//题目：
// 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

#include<iostream>

using namespace std;
//代码：
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    void EraseNode(ListNode* head,int cnt)
    {
        while(cnt>0){
            ListNode* next=head->next;
            delete head;
            //更新head
            head=next;
            cnt--;
        }
    }
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr || head->next==nullptr)return head;
        //先找到“非去重对象”的头结点
        ListNode* goal_head=head,*cur=head->next,*parent=head;
        bool flag=true;
        while(1)
        {
            int cnt=1;
            while(flag && cur && goal_head->val==cur->val)cur=cur->next,cnt++;
            if(flag && cur!=goal_head->next)
            {
                //删除结点+更新parent、cur和goal_head
                EraseNode(goal_head,cnt);//从goal_head结点开始删，一共删cnt个
                goal_head=cur,parent=goal_head;
                if(goal_head==nullptr)return nullptr;
                cur=goal_head->next;
            }    
            else 
            {
                cnt=1,flag=false;
                //找到头结点了，就是goal_head
                if(cur==nullptr)return goal_head;
                ListNode* cur_cur=cur->next;
                //判断cur是否是重复结点，若是，则去重
                while(cur_cur && cur->val==cur_cur->val)cur_cur=cur_cur->next,cnt++;
                if(cur->next!=cur_cur){
                    //删除cur
                    EraseNode(cur,cnt);
                    //更新parent->next
                    parent->next=cur_cur;
                    //更新cur和cur_cur
                    if(cur_cur==nullptr)return goal_head;
                    cur=cur_cur,cur_cur=cur->next;
                }
                else //则cur不是重复结点，更新parent、cur和cur_cur即可 
                {
                    if(cur_cur==nullptr)return goal_head;
                    parent=cur,cur=cur_cur,cur_cur=cur->next;
                } 
            }
        }
        return goal_head;
    }
};